#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/**
 *260. 只出现一次的数字 III
中等
698
相关企业
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。

示例 1：

输入：nums = [1,2,1,3,2,5]
输出：[3,5]
解释：[5, 3] 也是有效的答案。
示例 2：

输入：nums = [-1,0]
输出：[-1,0]
示例 3：

输入：nums = [0,1]
输出：[1,0]
 * */
// todo 其实这个思路不是把已经分组的数还原的 ,而是根据xor后的值的一位进行分组  最后分成了 两组
// 然后根据这两组分别xor 就剩下了那个最后两个落单的数了
vector<int> singleNumber(vector<int> &nums) {

    int end = 0;
    for (int i = 0; i < nums.size(); ++i) {
        end ^= nums[i];
    }
    //例如 [1,2,1,3,2,5] 最后求得的end值是 0110b  因为3 是011 5是0101 这俩xor不同才是1相同就是0  因此查看所有数字的位运算第二位就能区分
    // 为什么可以区分 我特么也不知到啊 他们说能区分出来
    int div = 1;//这个需要复制为1
    // int div=end&(-end);
    // 寻找位数
    while ((end & div) == 0)
        div = div << 1;//每次右移动一位

    int retA = 0;
    int retB = 0;
    for (int i = 0; i < nums.size(); ++i) {

        //这边操作需要加括号
        if ((nums[i] & div) == 0) {
            retA ^= nums[i];
        } else {
            retB ^= nums[i];
        }

    }

    return {retB, retA};
}
